package com.martain.leetcode.t22;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

/**
 * @author Martin
 * @version 1.0
 * @date 2020/12/27 5:01 下午
 */
public class T22 {

    List<String> result = new ArrayList<>();

    Integer Max  = 0;

    public List<String> generateParenthesis(int n) {
        Max = n*2;
        backtrack(Max,0,new StringBuffer());
        return result;
    }

    public void backtrack(int n, int tag, StringBuffer track)
    {
        if (n == 0){
            if (tag==0){
                result.add(track.toString());
            }
            return;
        }
        if (tag<Max/2){
            track.append("(");
            backtrack(n-1,tag+1,track);
            track.deleteCharAt(track.length()-1);
        }
        if (tag>=1){
            track.append(")");
            backtrack(n-1,tag-1,track);
            track.deleteCharAt(track.length()-1);
        }

    }

    public static void main(String[] args) {
        T22 t22 = new T22();
        List<String> strings = t22.generateParenthesis(3);
        System.out.println(strings);
    }

}
